The present invention generally relates to a graphics processor for drawing lines as a graphic image on a display device, for example, and more particularly relates to an apparatus that can draw relatively short lines in a shorter amount of time.
Thanks to remarkable progress of computer graphics technologies, the capabilities of graphics processors, such as the quantities of data processable per unit time, have tremendously improved. Under the circumstances such as these, the need for drawing an image at an even higher resolution goes on increasing day after day. Typical applications the computer graphics technologies have ever found include computer-aided design (CAD), computer-aided engineering (CAE) and computer games. Recently, however, those technologies have expanded their applications to presentation of maps on the display of a car navigation system using a global positioning system (GPS).
A car navigation system, in particular, often needs to present map information (e.g., roads, boundaries, etc. on the map) on the screen as a combination of many short lines, not just simple straight lines (or line segments). Also, the user's demand for accelerated line drawing by a graphics processor has been rising in the field of navigation systems. This is because he or she almost always wants to retrieve information about an area neighboring that currently presented on the screen as fast as possible.
As for the techniques of drawing lines by computer graphics technologies, see Yoshio Sato, “An Introduction to Graphics”, ASCII Publisher, pp. 46-56, for example.
Hereinafter, a known line-drawing method will be described with reference to FIGS. 25 and 26.
FIG. 25 illustrates a basic procedure taken by the known line-drawing method. Suppose a start point 100 with coordinates (Xs, Ys) and an end point 101 with coordinates (Xe, Ye) are given on the screen. In this case, to draw a line connecting the start and end points 100 and 101 together, a (linear) slope parameter, representing the slope of the line, needs to be calculated from these coordinates as |Ye-Ys|/|Xe-Xs|. Actually though, the line is drawn as a group of line segments 102 with a unit length that are joined together between the start and end points 100 and 101.
FIG. 26 illustrates a typical flow of the known line-drawing process. As shown in FIG. 20, first, in Step S100, the directional attribute of a line is determined. Specifically, the shifting direction of the line is known from the signs of the differences between the X Coordinates and between the Y coordinates of the start and end points 100 and 101, i.e., (Xe-Xs) and (Ye-Ys). Next, in Step S101, the slope parameter of the line is obtained by dividing the absolute value of the difference between the Y coordinates by that of the difference between the X coordinates, i.e., |Ye-Ys|/|Xe-Xs |. Then, in Step S102, it is determined whether or not the far end of the line being drawn has reached the end point 101. If the answer is NO, then the slope parameters obtained are sequentially added together from the start point 100 in the next Step S103.
As described above, in presenting detailed information about roads as a map on a car navigation system, for example, it is necessary to draw many short lines within a predetermined amount of time. However, the conventional line-drawing method needs to perform division operations for generating slope parameters as shown in FIG. 26. As is well known in the art, the division operations require high computational costs in the field of digital computations. That is to say, the hardware cost and the time for performing those operations are several times greater than addition operations. Thus, it is difficult for a car navigation system, which usually presents roads and so on using short lines, to draw those lines at sufficiently high speeds.